package leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class CQueue{
    Stack<Integer> stack1=null;
    Stack<Integer> stack2=null;
    public CQueue() {
        stack1=new Stack<>();
        stack2=new Stack<>();
    }

    public void appendTail(int value) {
        stack1.push(value);
    }

    public int deleteHead() {
        if (!stack2.isEmpty()){
            return stack2.pop();
        }else {
            if (stack1.isEmpty()){
                return -1;
            }else {
                while (!stack1.isEmpty()){
                    stack2.push(stack1.pop());
                }
            }
        }
        return stack2.pop();
    }
}
public class LeetCodeMain100 {
    public int numWays(int n) {
        if (n==0){
            return 0;
        }
        if (n==1){
            return 1;
        }
        int f1=1;
        int f2=2;
        for (int i = 3; i <= n; i++) {
            int f3=(f1+f2)%1000000007;
            f1=f2;
            f2=f3;
        }
        return f2;
    }
    public int fib(int n) {
        if (n==0){
            return 0;
        }
        int f1=0;
        int f2=1;
        for (int i = 2; i <= n; i++) {
            int f3=(f1+f2)%1000000007;
            f1=f2;
            f2=f3;
        }
        return f2;
    }
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix==null||matrix.length==0){
            return false;
        }

        int x=matrix.length-1;
        int y=0;
        int yLength=matrix[0].length-1;

        while (x>=0&&y<=yLength){
            if (matrix[x][y]<target){
                y++;
            }else if (matrix[x][y]>target){
                x--;
            }else {
                return true;
            }
        }
        return false;
    }
    public String replaceSpace(String s) {
        int length=s.length();
        StringBuffer buffer=new StringBuffer();
        for (int i = 0; i < length; i++) {
            char ch=s.charAt(i);
            if (ch==' '){
                buffer.append("%20");
            }else {
                buffer.append(ch);
            }
        }
        return buffer.toString();
    }
    public int[] reversePrint(ListNode head) {
        List<ListNode> list=new ArrayList<>();
        while (head!=null){
            list.add(head);
            head=head.next;
        }
        int i=0;
        int[] value=new int[list.size()];
        if (list.isEmpty()){
            return value;
        }
        while (!list.isEmpty()){
            value[i++]=list.remove(list.size()-1).val;
        }
        return value;
    }
    public int minArray(int[] numbers) {
        int length=numbers.length;
        if (length==1){
            return numbers[0];
        }
        for (int i = 1; i <= length-1; i++) {
            if (numbers[i]<numbers[i-1]){
                return numbers[i];
            }
        }
        return numbers[0];
    }
    public int count=0;
    public int movingCount(int m, int n, int k) {
        int[][] board=new int[m][n];
        DFS(board,k,0,0,m,n);
        return count;
    }
    public void DFS(int[][] board,int k,int x,int y,int m,int n){
        if (x<0||y<0||x>=m||y>=n||board[x][y]==1||!isTrue(x,y,k)){
            return;
        }
        board[x][y]=1;
        count++;
        DFS(board, k, x+1, y, m, n);
        DFS(board, k, x-1, y, m, n);
        DFS(board, k, x, y+1, m, n);
        DFS(board, k, x, y-1, m, n);

    }
    public boolean isTrue(int x, int y, int k) {
        int sum=0;
        while (x!=0){
            sum+=x%10;
            x=x/10;
        }
        while (y!=0){
            sum+=y;
            y/=10;
        }
        if (sum>=k){
            return false;
        }
        return true;
    }
}
